/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class PrintBinaryTree {
	public  static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public List<List<String>> printTree(TreeNode root) {
		int h = getHeight(root);
		int len = (1 << h) - 1;
		List<List<String>> result = new ArrayList<>(h);
		for (int i = 0; i < h; i++) {
			ArrayList<String> tmp = new ArrayList<>(len);
			for (int j = 0; j < len; j++) {
				tmp.add("");
			}
			result.add(tmp);
		}
		help(root, result, 0, len - 1, 0);
		return result;
	}

	private void help(TreeNode root, List<List<String>> result, int start, int end, int curHeight) {
		if (root == null) {
			return;
		}
		int mid = (start + end) / 2;
		result.get(curHeight).set(mid, root.val + "");
		help(root.left, result, start, mid - 1, curHeight + 1);
		help(root.right, result, mid + 1, end, curHeight + 1);
	}

	private int getHeight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int max = Integer.max(getHeight(root.left), getHeight(root.right));
		return max + 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode node1=new TreeNode(1);
		TreeNode node2=new TreeNode(2);
		TreeNode node3=new TreeNode(3);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(5);
		
		node1.left=node2;
		node1.right=node5;
		node2.left=node3;
		node3.left=node4;
		System.out.println(new PrintBinaryTree().printTree(node1));
	}

}
